<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      let arr = [4, 4, 6, 5, 3, 2, 8, 1];
      console.log(arr.toString());

      quickSort(arr, 0, arr.length - 1);
      console.log(arr.toString());

      function quickSort(arr, startIndex, endIndex) {
        // // 递归结束条件:startIndex大于或等于endIndex时
        if (startIndex >= endIndex) return;

        // 得到基准元素位置
        let pivotIndex = partition(arr, startIndex, endIndex);

        // 根据基准元素，分成两部分进行递归排序
        quickSort(arr, startIndex, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, endIndex);
      }

      function partition(arr, startIndex, endIndex) {
        // 取第1个位置(也可以选择随机位置)的元素作为基准元素
        let pivot = arr[startIndex];
        let left = startIndex;
        let right = endIndex;

        while (left != right) {
          //控制right 指针比较并左移
          while (left < right && arr[right] > pivot) {
            right--;
          }
          //控制left 指针比较并右移
          while (left < right && arr[left] <= pivot) {
            left++;
          }

          // 交换left 和right指针所指向的元素
          if (left < right) {
            let p = arr[left];
            arr[left] = arr[right];
            arr[right] = p;
          }
        }
        // pivot 和指针重合点交换。
        arr[startIndex] = arr[left];
        arr[left] = arr[pivot];

        return left;
      }
    </script>
  </body>
</html>
